#ifndef __TYPED_DIRECTED_GRAPH__
#define __TYPED_DIRECTED_GRAPH__

#pragma once

#include <set> // std::set
#include <vector> // std::vector
#include <utility> // std::pair
#include <sstream> // std::stringstream
#include <fstream> // std::ofstream
#include <map>

#include <boost/tuple/tuple.hpp> // boost::tuple
#include <boost/unordered_map.hpp> // for consistency reasons, we use boost::unordered_map instead of std::unordered_map
#include <boost/functional/hash.hpp> // boost::hash_combine
#include <boost/heap/fibonacci_heap.hpp> // boost::heap::fibonacci_heap

#include "geo_defines.h" // geo_cand_rtree; the better implementation is to inherit class "typed_directed_graph" and put this function in a newly derived class
						 // geo_cand_rtree: 更好的实现方法是继承
#include "k_median.h"

#define RID


//================================================================================
// Notations:
//	Starting and ending vertices are the both endpoints of a directed edge.
//	起始点和终点都是一条有向边的端点
//	Source and target vertices are the vertices of a path.
//	源点和目标点是一条路径的点
//	Each vertex consist of an index number and a type, which is one of the following (must be lower case):
//	每一个点包含一个序列号，以及一个类型标识，它只能是下列四种情况：
//		v - ordinary vertex;
//		f - facility vertex;
//		c - candidate vertex;
//		r - reference location vertex.
//	The index number of a vertex is a non-negative and mutually exclusive integer value, and inconsecutive values is permitted.
//	顶点的序列号是一个非负值，并且不会相互重复。不连续的值是不被允许的。
// Implementation:
//	Parallel edge is not allow, which is guaranteed via std::set for out-edges.
//  不允许存在平行边,通过使用set 得到避免
//	Use adjacent edges for each vertex, with redundant vertices of in-edges aiming at edge split and vertex replacing.
//  每个顶点都有邻边集，并且其中含有冗余的入边顶点，这是为了便于边的分割以及顶点的替换。
//	Reference locations are created onto graph as virtual vertices, each of which has a zero-distance unidirection edge from it to the overlapped vertex.
//  参考位置被当作虚拟顶点添加在图上，并且如果它覆盖了一个点，那么它会有一条到它所覆盖的点的一条单向边，它的距离为零。

// Remark:
// 备注：
//	Vertex ID is represented by int type, whose reason is that int can hold 2*10^9 verties with 4 bytes, while std::string needs 24/36 bytes in 32/64 bit system.
//	顶点ID使用整型存储
//	Facilities are strictly forbidden to overlap with each other.
//  设备点之间禁止相互覆盖
//	Candidates are strictly forbidden to overlap with facilities or each other.
//  候选设备之间禁止覆盖，同时也禁止覆盖设备点
//	The edges file format must be "edge_id vs_id ve_id dist".
//	The facilities file format must be "fac_id vs_id ve_id dist_vs_fac dist_fac_ve".
//	The candidates file format must be "cand_id vs_id ve_id dist_vs_cand dist_cand_ve lon lat".
//	The reference locations file format must be "refloc_id vs_id ve_id dist_vs_refloc dist_refloc_ve prob lon lat".

//================================================================================
// vertex associated with type

struct vertex
{
	int id; // vertex index number
	char type; // vertex type: 'v', 'f', 'c', 'r'

	vertex()
		: id(-1) // default with invalid id (-1)
		, type('v') {} // default is ordinary vertex 'v'

	vertex(int id_in, char type_in)
		: id(id_in)
		, type(type_in) {}

	vertex(const vertex &rhs)
	{
		if (this == &rhs)
			return;
		id = rhs.id;
		type = rhs.type;
	}

	vertex& operator=(const vertex &rhs)
	{
		if (this == &rhs)
			return *this;
		id = rhs.id;
		type = rhs.type;
		return *this;
	}

	bool operator<(const vertex &rhs) const
	{
		if (type == rhs.type) // if with the same type
			return id < rhs.id; // first compare id
		else
			return type < rhs.type; // then compare type
	}

	bool operator==(const vertex &rhs) const
	{
		return id == rhs.id && type == rhs.type;
	}

	// boost::hash is implemented by calling the function hash_value
	friend std::size_t hash_value(const vertex &v)
	{
		std::size_t seed = 0;
		boost::hash_combine(seed, v.id);
		boost::hash_combine(seed, v.type);
		return seed;
	}
};

//================================================================================
// directed out-edge with edge weight (distance) but without starting vertex
// 有向出边，带有权重，但是没有起点

struct out_edge
{
	vertex ve; // ending vertex 终点
	double dist; // edge weight (distance)

	out_edge()
		: ve() // ve.id is default -1
		, dist(1.0f) {} // default weight

	out_edge(int ve_id, char ve_type, double dist_in)
		: ve(ve_id, ve_type)
		, dist(dist_in) {}

	out_edge(const out_edge &rhs)
	{
		if (this == &rhs)
			return;
		ve = rhs.ve;
		dist = rhs.dist;
	}

	bool operator<(const out_edge &rhs) const
	{
		return ve < rhs.ve;
	}

	bool operator==(const out_edge &rhs) const
	{
		return ve.id == rhs.ve.id && ve.type == rhs.ve.type && dist == rhs.dist;
	}
};

//================================================================================
// a tuple that represents a directed edge
// 代表一条有向边的元组

typedef boost::tuple < vertex, // starting vertex
	vertex, // ending vertex
	double > // edge weight (distance)
directed_edge;

enum directed_edge_element { VS = 0, VE, DIST };

//================================================================================
// hash map for <vertex, adjacent edges> is implemented based on unordered_map;
// 顶点与邻边借助于 unordered_map 实现
// adjacent edges is a pair std::sets of out-edges (out_edge) and in-edges (vertex)
// 邻边通过set的pair来实现

typedef std::pair < std::set<out_edge>, // out-edges
	std::set<vertex> > // starting vertice of in-edges
vs_adjacent_edges;

typedef boost::unordered_map < vertex, // starting vertex
	vs_adjacent_edges > // adjacent edges of starting vertex
adjacent_edges_hash_map;

//================================================================================
// vertex that has been inserted to split an original (ordinary) edge of graph
// 已经被插入的用来分割原始边的顶点

struct inserted_vertex
	: public vertex
{
	double dist_vs; // the distance from vs to vertex "inserted"  从起点到插入点的距离

	inserted_vertex(int id_in, char type_in, double dist_vs_in)
		: vertex(id_in, type_in)
		, dist_vs(dist_vs_in) {}
};

//--------------------------------------------------------------------------------
// hash map for split edges with the corresponding inserted vertices is implemented based on unordered_map
// hash map 用来区分各个边，值为边上的插入点

typedef boost::unordered_map < std::string, // starting and ending vertice string, whose format must be "vs_id-ve_id"
	std::vector<inserted_vertex> > // vertices that have been inserted to split <vs, ve>
split_edges_hash_map;

//================================================================================
// target vertex associated with the shortest path distance from source vertex
// 从源顶点开始的与相应最短边相关的目标顶点

struct target_vertex
	: public vertex
{
	double dist; // the shortest path distance from source vertex 路径距离

	target_vertex(int id_in, char type_in, double dist_in)
		: vertex(id_in, type_in)
		, dist(dist_in) {}

	target_vertex(const target_vertex &rhs)
	{
		if (this == &rhs)
			return;
		id = rhs.id;
		type = rhs.type;
		dist = rhs.dist;
	}

	// remark: the same vertex validation is not implemented
	// 注意：同样的顶点，，，，没有实现
	bool operator>(const target_vertex &rhs) const
	{
		return dist > rhs.dist; // only compare shortest distance
	};
};

//--------------------------------------------------------------------------------
// a mutable fibonacci min-heap for ordering target vertices without indication of source vertex, which is used in dijkstra algorithm;
// 一个可变的斐波那契堆用来对target顶点进行排序，不需要指出source顶点，在迪杰斯特拉算法中使用
// an assistant hash map for storing vertices and the corresponding min-heap handles & current shortest distance from source vertex;
// 一个辅助的 hash map 用来存储顶点以及相应的最小堆和当前最短距离
// a hash map for storing vertices with definite shortest distance from source vertex
// 一个hash map用来存储顶点以及最终最短距离

typedef boost::heap::fibonacci_heap < target_vertex, // target vertex associated with the (current) shortest path distance from source vertex to itself
	boost::heap::compare < std::greater < target_vertex > >, // shift default max-heap to min-heap by replacing "less" function with "greater"
	boost::heap::stable <false> > // mutable min-heap
vertex_min_heap;

typedef vertex_min_heap::handle_type vertex_handle; // handle of target vertex in the min-heap 最小堆中的target顶点的句柄

typedef boost::unordered_map < vertex, // target vertex (base class is enough)
	std::pair < vertex_handle, // handle of target vertex in the min-heap 最小堆的句柄
	double > > // current shortest distance from source vertex to target vertex 当前最小距离
target_hash_map; // assistant hash map 起到帮助作用的hash map

typedef boost::unordered_map < vertex, // target vertex with definite shortest path distance from source vertex
	double > // the definite shortest path distance
definite_hash_map;

//================================================================================
// candidate associated with the expected reduction of distance (ERD)
// candidate结构，与期望缩减距离相关

struct candidate
{
	int id; // candidate index number
	double ERD; // the expected reduction of distance (ERD)

	candidate()
		: id(-1)
		, ERD(0.0f) {}

	candidate(int id_in, double ERD_in)
		: id(id_in)
		, ERD(ERD_in) {}

	// remark: the same candidate validation is not implemented
	bool operator<(const candidate &rhs) const
	{
		return ERD < rhs.ERD; // only compare ERD
	};
};

//--------------------------------------------------------------------------------
// a mutable fibonacci max-heap for ordering candidates by ERD;
// 通过ERD进行排序的斐波那契最大堆
// an assistant hash map for storing max-heap handles and ERDs of candidates
// 一个起到辅助作用的 hash map，它存储着 candidate 的ERD和堆的句柄

typedef boost::heap::fibonacci_heap<candidate> cand_max_fibonacci_heap;

typedef cand_max_fibonacci_heap::handle_type cand_handle; // handle of candidate in the fibonacci max-heap

typedef boost::unordered_map < int, // candidate id
	std::pair < cand_handle, // handle of candidate in the fibonacci max-heap
	double > > // ERD of candidate
cand_hash_map; // assistant hash map

//================================================================================
// facilities associated with the endpoints
// 与终点相关联的设备

typedef boost::unordered_map < int, // facility id
	boost::tuple < int, // vs_id
	int, // ve_id
	double, // vs_dist
	double > > // ve_dist
fac_hash_map;//设备的hash表，键值是设备id，映射到一个元组，包含起点id、终点id、到起点的距离和到终点的距离

typedef boost::unordered_map < int, // facility id
	boost::tuple < int, // vs_id
	int, // ve_id
	double, // vs_dist
	double, // ve_dist
	double, // lon
	double > > // lat
fac_ex_hash_map; //带有经度和纬度

enum fac_hash_map_element { VS_ID = 0, VE_ID, VS_DIST, VE_DIST, F_LON, F_LAT };



//================================================================================
// base classes of all event visitors, which are function objects and invoked during traversing graph by dijkstra algorithm;
// 所有事件观察者的基类，它是函数对象当执行迪杰斯特拉算法时将会被调用
// "top event" occurs when the shortest path distance of any target vertex (from the source vertex) is determined;
// "top event" 当任意目标位置的最短距离被确定时都会发生
// "extend event" occurs when new out-vertices of the current target vertex are being extended
// "extend event" 当当前目标顶点的新 out-verttices 被扩展时发生

class top_event_visitor
{
public:
	virtual bool // return "true" to terminate graph traversal (by dijkstra algorithm); otherwise (false), continue the traversal
		         //返回'true' 终止图的遍历，返回‘false'继续
		operator()(const target_vertex &v, // top target vertex
		const definite_hash_map &hash_map) = 0; // the hash map for storing vertices with definite shortest distance from source vertex
												// hash map 用来存储带有最短距离的顶点
};

class extend_event_visitor
{
public:
	virtual bool // return "true" to terminate graph traversal (by dijkstra algorithm); otherwise (false), continue the traversal
				 // 返回'true'终止遍历，否则继续
		operator()(const target_vertex &v, // the vertex has definite shortest path distance
										   // 带有最短距离的顶点
		const out_edge &e) = 0; // the extended out-edge from the target vertex
								// 从target顶点扩展的出边
};

//================================================================================
// typed directed graph

class typed_directed_graph
{
public:
	std::ofstream *out_file; // the output file for testing status texts; default value is NULL, which means no need to output status texts
							 //用来测试状态的输出文件，默认值为NULL，代表不需要输出状态
	bool is_to_bidirectional; // indicate whether to convert (true) undirected graph into bidirectional graph or not (false)
							  //指出是否将无向图转换为双向图
	bool is_graph_init; // indicate whether graph is succussfully initialized (true) or not (false)
						//指示该图是否被成功初始化
	bool is_facilities_deployed; // indicate whether facilities are succussfully deployed (true) or not (false)
								 //指示设备是否被成功部署
	bool is_candidates_deployed; // indicate whether candidates are succussfully deployed (true) or not (false)
								 //指示待替换设备是否被成功部署
	adjacent_edges_hash_map adjacent_edges; // vertices (key) each of which binds the corresponding out-edges and in-edges (value)
											//邻边,键值是顶点id，映射到与它相邻的边上
	split_edges_hash_map split_edges; // split edges with the corresponding inserted vertices
									  //用相应插入点来分割边
public:
	typed_directed_graph()
		: is_to_bidirectional(false)
		, is_graph_init(false)
		, is_facilities_deployed(false)
		, is_candidates_deployed(false) {}
	virtual ~typed_directed_graph(){}


public:
	void set_testing(std::ofstream *out_file_in = NULL) { out_file = out_file_in; };
	void set_to_bidirectional(bool to_bidirectional) { is_to_bidirectional = to_bidirectional; };
	bool get_is_facilities_deployed() { return is_facilities_deployed; };
	bool get_is_candidates_deployed() { return is_candidates_deployed; };
	bool init_graph(const char *edges_file_path); /*********************/
	bool deploy_facilities(const char *facs_file_path, std::vector<int> &fac_ids);
	bool deploy_facilities(const char *facs_file_path, fac_hash_map *hash_map = NULL); /*********************/
	//
	bool deploy_facilities(const wh::facility_info_map& facility_info, fac_hash_map* hash_map = NULL); /*********************/
	//
	bool deploy_facilities_ex(const char *facs_file_path, fac_ex_hash_map *hash_map);
	bool deploy_candidates(const char *cands_file_path, std::vector<int> &cand_ids);
	void insert_vertex(const vertex &vs, const vertex &ve, const vertex &inserted, double dist_vs_inserted, double dist_inserted_ve,
		std::vector<directed_edge> *removed_edges = NULL, std::vector<directed_edge> *inserted_edges = NULL, bool is_replace_overlap = false); /*********************/
	void restore_graph(const vertex &inserted, const std::vector<directed_edge> &removed_edges, const std::vector<directed_edge> &inserted_edges); /*********************/
	void dijkstra(const vertex &source, top_event_visitor *top_visitor = NULL, extend_event_visitor *extend_visitor = NULL); /*********************/
	void dijkstra(const vertex& source, std::map<int, double> & dist_map, wh::fac_ref_dist_map& fac_ref_dist, int, const double);

	// the better implementation is to inherit class "typed_directed_graph" and put this function in a newly derived class
	// 更好的方法
	bool deploy_candidates_rtree(const char *cands_file_path, geo_cand_rtree &cand_rtree, boost::unordered_map<int, geo_point> &cand_geos);

public:
	void overlap_vertex(const vertex &overlapped, const vertex &inserted, std::vector<directed_edge> *removed_edges = NULL,
		std::vector<directed_edge> *inserted_edges = NULL, bool is_replace_overlap = false); /**********************/
/**/bool split_edge(const vertex &vs, const vertex &ve, const vertex &inserted, double dist_vs_inserted, double dist_inserted_ve,
		std::vector<directed_edge> *removed_edges = NULL, std::vector<directed_edge> *inserted_edges = NULL);
	void split_split_edge(const split_edges_hash_map::iterator &iter, int vs_id, int ve_id, const vertex &inserted,
		double dist_vs, double dist_ve, std::vector<directed_edge> *removed_edges, std::vector<directed_edge> *inserted_edges); /********************/
	void replace_vertex(const vertex &replaced, const vertex &inserted, std::vector<directed_edge> *removed_edges = NULL,
		std::vector<directed_edge> *inserted_edges = NULL);
};

#endif
